"""
https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

315. 计算右侧小于当前元素的个数
困难
相关标签
相关企业
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

 

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：

输入：nums = [-1]
输出：[0]
示例 3：

输入：nums = [-1,-1]
输出：[0,0]
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
"""

from typing import List


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        """
        可解决，但复杂度为O(n^2)较高
        """
        res=[]
        for left in range(len(nums)-1):
            count=0
            for right in range(left+1,len(nums)):
                if nums[left]>nums[right]:
                    count+=1
            res.append(count)
        res.append(0)
        return res

if __name__=='__main__':
    s = Solution()
    nums = [-1,-1]
    res=s.countSmaller(nums)
    print(res)
    pass